/*# 8 月 25 日课后作业

## 选择题（多选）

1. 逆序数组的标准库函数是：B

A. reversed；

B. reverse；

C. sort；

D. sorted；

---

2. 关于 C++ 指针，以下说法正确的是：BC

A. 指针变量用于保存同类型其它变量的位置；

B. int *pn 用于定义一个整数指针变量 pn；

C. 在变量前使用 & 表示读取该变量的在内存中的位置，也就是它的地址；

D. 在指针变量前使用 *，表示向指针指向的位置写入数据；


## 填空题

1. 十进制数字 8 4 2 1 的二进制分别是：__1000_______、__100_______、__10_______、__1_______

2. 以下代码执行后，变量 `n` 的值是：____9_____

```c++
int n = 10;
int *p_n = &n;

n += 1;
*p_n -= 2;
```

3. 对于下面的函数，把 `pi` 传递给 `fn` 的写法是：______fn(&pi)_________

```c++
double pi = 3.14;

void fn(double *p_d) {
  *p_d = (*p_d) * 10;
}
```

4. 对于整数数组 `vector<int> numbers {5, 1, 2, 4, 7}`，C++ 中遍历 `numbers` 的简易 `for` 循环写法是：

```c++
for (auto i : numbers) {
    cout<<i<<endl;
}
```

## 算法题

1. 假设有一个整数数组 `coins` 表示各种面额的硬币，编写一个函数 `nonConstructibleChange`，让它返回这些硬币不能找出来的零钱的最小值。

例如：

如果 `coins` 等于 `[1, 2, 5]`，说明我们有三个面额是 1, 2, 5 的硬币，那么，这三个硬币不能找出来的零钱最小值是 4。*/
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int nonConstructibleChange(vector<int> coins) {
    sort(coins.begin(), coins.end());

    for( int n = 1; true; n++ )
    {
        for( int i = 0; i < coins.size(); i++)
        {
            if( n < coins[i] )
                return n;
            else if( n > coins[i] )
                n -= coins[i];
            else //n == coins[i]
                break;
        }
    }
}


//2. 考虑我们课上编写的十进制转换二进制的函数：

vector<int> decToBin(int n) {
  // 辗转相除
  vector<int> result; // 计算结果
/*
  while (n / 2 != 0) {
    result.push_back(n % 2);
    n = n / 2;
  }

  // n / 2 == 0
  result.push_back(n % 2);
*/
  do{
    result.push_back(n % 2);
    n = n / 2;
  }while (n / 2 != 0); 

  reverse(result.begin(), result.end());

  return result;
}


//我们如何能修改一下这个程序，可以直接通过 `while` 循环收集到所有的二进制位，而不用在循环之后，再单独 `push_back` 最后一位呢？

